export const enum Color {
    RED = 'RED',
    BLACK = 'BLACK'
}
export class RBNode<T>  {
    // 高度默认是1
    height = 1
    value: T | undefined
    left: RBNode<T> | null
    right: RBNode<T> | null
    parent: RBNode<T> | null
    color = Color.RED
    constructor(value: T, parent: RBNode<T> | null, left: RBNode<T> | null, right: RBNode<T> | null) {
        this.value = value;
        this.parent = parent
        this.left = left;
        this.right = right;
    }

    /**
     * 获取平衡因子
     */
    fac() {
        return this.heightDiff()
    }

    /**
     * 判断当前节点是否平衡
     */
    isBalance() {
        // 高度相减不能超过 1 => -1 <= h <= 1
        return Math.abs(this.heightDiff()) <= 1
    }

    /**
     * 左右子树高度差
     */
    heightDiff() {
        const leftHeight = this.left === null ? 0 : this.left!.height
        const rightHeight = this.right === null ? 0 : this.right!.height
        // 左高度减去右子树高度
        return leftHeight - rightHeight;
    }

    /**
     * 更新当前节点的高度
     */
    updateHeight() {
        const leftHeight = this.left === null ? 0 : this.left!.height
        const rightHeight = this.right === null ? 0 : this.right!.height
        // 左右子树高度差加一
        this.height = 1 + Math.max(leftHeight, rightHeight)
    }

    /**
     * 获取获取该节点最高的孩子
     */
    getTallChild() {
        // 获取高度差
        const isLeftHeight = this.heightDiff();

        if (isLeftHeight > 0) {
            // 左高
            return this.left;
        } else if (isLeftHeight < 0) {
            // 右高
            return this.right;
        } else {
            // 高度一样，返回是左孩子还是右孩子
            return this.isLeft() ? this.left : this.right
        }
    }

    /**
     * p的右孩子
     * @param p 
     */
    isRight(): boolean {
        if (this.parent === null) return false
        return this.parent.right === this
    }

    /**
     * p的左孩子
     * @param p 
     */
    isLeft() {
        if (this.parent === null) return false
        return this.parent.left === this;
    }

    /**
     * 是不是叶子节点
     */
    isLeaf() {
        return this.left == null && this.right == null
    }

    /**
     * 是不是根节点
     */
    isRoot() {
        return this.parent === null
    }

    /**
     * 节点度为2
     */
    hasTwoChild() {
        return this.left !== null && this.right !== null
    }

    /**
     * 节点度为1
     */
    hasOneChild() {
        return (this.left === null && this.right !== null) || (this.left !== null && this.right === null)
    }

    /**
     * 是否有右孩子
     */
    hasRightChild() {
        return this.right !== null
    }

    /**
     * 是否右左孩子
     */
    hasLeftChild() {
        return this.left !== null
    }

   

    /**
     * 获取兄弟节点
     */
    sibling() {
        // 当前节点是左孩子
        if (this.isLeft()) {
            // 返回父亲的右孩子
            return this.parent?.right;
        }

        // 当前节点是右孩子
        if (this.isRight()) {
            return this.parent?.left;
        }
        // 左或者右孩子被删除了, 哪个不为空就是其兄弟节点
        return this.parent?.left || this.parent?.right;
    }

    /**
     * 获取叔叔节点
     */
    uncle() {
        // 如果有父亲，那么返回父亲的兄弟，就是叔叔节点
        if (this.parent !== null) {
            return this.parent.sibling();
        }
        return null
    }


}

    // /**
    //  * 红黑树中删除的都是叶子节点, 删除一度或者二度的节点,最终都是找到替换的节点将其删除了
    //  * 删除节点之后调节平衡
    //  */
    // afterRemove2(node: RBNode<T>) {
    //     /**
    //         1. red节点, 不处理
    //         2. black节点(2个red),删除的是替代它的节点(前驱或者后继), 也不用管
    //         3. black节点(1个red)
    //         4. black节点(0个red)
    //      */
    //     // 递归导致的
    //     if (node == null) return;

    //     // 条件1,如果删除的是红色的节点,不处理
    //     if (node.isRed()) return;

    //     // 条件3, 只有一个节点 并且是 red节点
    //     if (node.hasOneChild() && (node.left?.isRed() || node.right?.isRed())) {
    //         // 只需要将替换的节点染成黑色即可(可能是左,也可能是右)
    //         black(node.left || node.right)
    //         return
    //     }

    //     // 删除的是黑色的叶子节点

    //     // 1. 删除节点的sibling至少有一个red节点
    //     const sibling = node.sibling();

    //     // 兄弟节点至少有一个子节点为红色
    //     if (sibling?.hasRedChild()) {
    //         const parent = node.parent!;
    //         if (sibling.left) {
    //             // 有左孩子

    //             // parent进行右旋转
    //             this.rotateRight(parent)

    //             // 更改颜色

    //             // 新的中心节点继承父元素的颜色
    //             colorOf(sibling, parent.colorOf())

    //             // 中心节点的两边变为黑色
    //             black(sibling.left)
    //             black(parent)
    //         } else {
    //             // 有右孩子, 左孩子不为红

    //             // sibling进行左旋转
    //             this.rotateLeft(sibling)
    //             // parent进行右旋转
    //             this.rotateRight(parent)

    //             // 新的中心节点继承父元素的颜色
    //             colorOf(sibling.right, parent.colorOf())
    //             // 中心点的两边变为黑色
    //             black(sibling)
    //             black(parent)
    //         }

    //         return
    //     } else if (sibling?.colorOf() !== Color.RED) {
    //         // TODO... 修改判断条件
    //         // 没有一个子节点为红色, 兄弟节点不是红色

    //         const parent = node.parent!
    //         // sibling染成红色
    //         red(sibling!)
    //         black(parent)

    //         // parent可能也会下溢, 将parent当作删除的节点, 也要进行删除后的处理
    //         this.afterRemove(parent)
    //     } else {
    //         // 兄弟节点是红色
    //         const parent = node.parent

    //         red(sibling)
    //         black(parent)
    //     }


    // }